/**
 * 
 */
package dp.passed2;

/**
 * @author xyyi
 *
 */
public class DecodeWays {

    /**
    A message containing letters from A-Z is being encoded to numbers using the following mapping:

    'A' -> 1
    'B' -> 2
    ...
    'Z' -> 26

    Given an encoded message containing digits, determine the total number of ways to decode it.

    For example,
    Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

    The number of ways decoding "12" is 2.
    
    /*
    DP
    count[n] = count[n - 1] if s[n] is valid number to represent a char
    or count[n] = count[n - 1] + count[n - 2] if s[n] is valid number to represent a char and s[n]s[n-1] is a valid number to represent a char
     */
    public int numDecodings(String s) {
        if (s == null || s.isEmpty())
            return 0;
        int p2 = 0, p1 = 1, curr = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '0')
                curr = p1;
            if (i >= 1
                    && (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s
                            .charAt(i) <= '6'))) {
                curr += p2;
            }
            if (curr == 0)
                return 0;
            p2 = p1;
            p1 = curr;
            curr = 0;
        }

        return p1;
    }

    public int numDecodings1(String s) {
        if (s == null || s.isEmpty() || !isValid(s.charAt(0)))
            return 0;
        if (s.length() == 1) {
            return 1;
        }
        int p2 = 1, p1 = 0, counter = 0;
        if (isValid(s.charAt(1))) {
            p1 = p2;
        }
        if (isValid(s.charAt(0), s.charAt(1))) {
            p1++;
        }

        for (int i = 2; i < s.length(); i++) {
            counter = isValid(s.charAt(i)) ? p1 : counter;
            counter = isValid(s.charAt(i - 1), s.charAt(i)) ? counter + p2
                    : counter;
            if (counter == 0)
                return 0;
            p2 = p1;
            p1 = counter;
            counter = 0;
        }

        return p1;
    }

    private boolean isValid(char c) {
        return c != '0';
    }

    private boolean isValid(char c1, char c2) {
        return c1 == '1' || (c1 == '2' && c2 <= '6');
    }

    /**
     * 
     */
    public DecodeWays() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }

}
